package cn.genmer.test.security.algorithm.similarity.ld;

/**
 * LD(Levenshtein Distance) 动态规划优化
 * https://zhuanlan.zhihu.com/p/80682302
 */
public class LD {
    public static void main(String[] args) {
        System.out.println(getAddressSimilarity("大镇", "大朗镇"));
    }

    /**
     * 计算相似度
     * @param a
     * @param b
     * @return
     */
    public static double getAddressSimilarity(String a, String b){
        return 1 - (double)minDistance(a, b)/Math.max(a.length(), b.length());
    }

    /**
     * 得到编辑次数
     * @param s1
     * @param s2
     * @return
     */
    public static int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        // base case
        for (int i = 1; i <= m; i++)
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;
        // 自底向上求解
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (s1.charAt(i-1) == s2.charAt(j-1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(
                            dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1,
                            dp[i-1][j-1] + 1
                    );
        // 储存着整个 s1 和 s2 的最小编辑距离
        return dp[m][n];
    }

    static int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}
